W6. Arithmetic-Logic Unit Construction, Latch Circuits, Finite State Machines

Author

Artem Burmyakov

Published

October 10, 2025

Quiz | Flashcards

1. Summary

1.1 Arithmetic-Logic Unit (ALU) Construction

An Arithmetic-Logic Unit (ALU) is a fundamental digital circuit within a computer’s central processing unit (CPU) that performs arithmetic and bitwise logic operations on integer binary numbers. It is the computational core of the processor.

1.1.1 Basic ALU Organization

A simple ALU can be designed to handle a specific set of instructions. The core idea is to have separate circuits for each operation and use a multiplexer (MUX) to select the correct output based on a control signal called an opcode (operation code).

For an ALU that performs addition (+), subtraction (-), multiplication (*), and equality comparison (==), the organization would be as follows:

  • Two input arguments (Arg. 1, Arg. 2) are fed in parallel to four distinct circuits.
  • Each circuit computes its specific function: one for addition, one for subtraction, etc.
  • The results from all four circuits are sent to the inputs of a multiplexer.
  • The opcode is used as the select signal for the MUX. It determines which of the four results is passed to the final output, Q.

1.1.2 4-Bit Adder Circuit

A binary adder is a circuit that performs the addition of binary numbers. A 4-bit adder adds two 4-bit numbers. A common implementation is the ripple-carry adder, which is constructed by cascading full adders.

  • Full Adder: A combinational circuit that adds three bits: two input bits (\(A\) and \(B\)) and a carry-in bit (\(C_{in}\)). It produces two outputs: a sum bit (\(S\)) and a carry-out bit (\(C_{out}\)). The logic involves XOR gates for the sum and AND/OR gates for the carry.
  • Ripple-Carry Adder: For a 4-bit adder (e.g., adding \(A_4A_3A_2A_1\) and \(B_4B_3B_2B_1\)), four full adders are connected in series.
    1. The first full adder adds the least significant bits (\(A_1, B_1\)) with a \(C_{in}\) of 0. It produces the first sum bit (\(q_1\)) and a carry-out (\(c_{out1}\)).
    2. This carry-out (\(c_{out1}\)) is “rippled” to become the carry-in for the second full adder, which adds \(A_2, B_2,\) and \(c_{out1}\) to produce \(q_2\) and \(c_{out2}\).
    3. This process continues for all bits, with the carry-out of one stage feeding the carry-in of the next. The final carry-out from the last full adder can be used to detect an overflow.

1.1.3 4-Bit Subtractor Circuit

Subtraction in binary can be performed by adding the two’s complement of the subtrahend. A 4-bit subtractor can be built using a 4-bit adder with a slight modification. To calculate \(A - B\), we compute \(A + (\text{two's complement of } B)\).

The two’s complement of a number is found by inverting all its bits (one’s complement) and then adding 1. The circuit for \(A - B\) can be implemented as:

  1. Invert each bit of the second number, \(B\), using NOT gates.
  2. Feed the inverted bits of \(B\) and the bits of \(A\) into a 4-bit adder.
  3. Set the initial carry-in (\(C_{in}\)) to the first full adder to 1. This handles the “+1” part of the two’s complement operation.

1.1.4 Binary Multipliers

Binary multiplication is similar to decimal multiplication and involves generating and then summing partial products.

  • Single-Bit Case: Multiplying two single bits, \(a \times b\), is equivalent to the logical AND operation. The result is 1 only if both \(a\) and \(b\) are 1. The circuit for this is a single AND gate.
  • 2-by-2 Bit Case: To multiply two 2-bit numbers, \(A = a_1a_0\) and \(B = b_1b_0\):
    1. Generate partial products by ANDing each bit of \(A\) with each bit of \(B\). This results in four partial products: \(a_0b_0\), \(a_1b_0\), \(a_0b_1\), and \(a_1b_1\).
    2. Arrange the partial products according to their bit positions (place value) and sum them using adders (half-adders and full-adders). The result can be up to 4 bits long.
  • 4-by-4 Bit Multiplier: This extends the same principle. A 4-by-4 multiplier takes two 4-bit numbers and produces an 8-bit result.
    1. Partial Product Generation: An array of 16 AND gates is used to compute all the partial products (\(a_ib_j\) for \(i,j \in \{0,1,2,3\}\)).
    2. Summation: A complex structure of half-adders and full-adders is used to sum the partial products. This is often done in a tree-like structure to reduce propagation delay.
1.1.5 4-by-4 Bit Equality Checker

An equality checker determines if two binary numbers are identical. For two 4-bit numbers, \(A = A_3A_2A_1A_0\) and \(B = B_3B_2B_1B_0\), they are equal if and only if each corresponding pair of bits is equal (\(A_i = B_i\) for all \(i\)).

This can be implemented using XNOR gates.

  • An XNOR gate outputs 1 only if its two inputs are the same.
  • Each pair of bits (\(A_0, B_0\)), (\(A_1, B_1\)), etc., is fed into a separate XNOR gate.
  • The outputs of all four XNOR gates are then fed into a 4-input AND gate.
  • The final output of the AND gate will be 1 only if all four XNOR gates output 1, which means all bit pairs are identical.

1.2 Latch Circuits and Memory

Unlike combinational logic circuits (like adders) whose outputs depend solely on their current inputs, sequential logic circuits have outputs that depend on both current inputs and previous states. They have a memory property. The fundamental building block of this memory is the latch.

1.2.1 Universal Logic Gates

While there are many basic logic gates (AND, OR, XOR, etc.), all of them can be constructed from only NAND gates or only NOR gates. Because of this property, NAND and NOR gates are called universal gates. They are crucial for building sequential circuits like latches.

1.2.2 SR Latch from NOR Gates

An SR Latch (Set-Reset Latch) is one of the simplest sequential circuits. It can be constructed using two cross-coupled NOR gates.

  • The output of the top NOR gate is fed back as an input to the bottom NOR gate.
  • The output of the bottom NOR gate is fed back as an input to the top NOR gate.
  • This feedback loop is what allows the circuit to store a state.
  • The circuit has two inputs, S (Set) and R (Reset), and two outputs, Q and \(\bar{Q}\) (which is typically the inverse of Q).

1.2.3 SR Latch Behavior Analysis

The state of the SR latch is determined by the inputs S and R.

  • Set (S=1, R=0): This input combination forces the output Q to 1 (and \(\bar{Q}\) to 0). This is called the set state.
  • Reset (S=0, R=1): This forces the output Q to 0 (and \(\bar{Q}\) to 1). This is the reset state.
  • Hold/Store (S=0, R=0): When both inputs are 0, the latch maintains its previous state. The feedback loop keeps the outputs stable. If Q was 1, it remains 1; if it was 0, it remains 0. This is the memory property.
  • Illegal/Forbidden State (S=1, R=1): This combination forces both Q and \(\bar{Q}\) to 0. This violates the logical condition that \(\bar{Q}\) should be the inverse of Q. More importantly, if S and R then change to 0 simultaneously, the next state is unpredictable (a race condition), making this input combination invalid.

The SR latch is also known as a bistable multivibrator because it has two stable states (Q=0 and Q=1). It can store one bit of data.

1.2.4 D Latch (Enable Latch)

To solve the illegal input problem of the SR latch, the D Latch (Data Latch or Enable Latch) was developed. It has two inputs: D (Data) and E (Enable).

  • When the Enable (E) input is high (1), the latch is transparent. The output Q simply follows the input D. If D is 1, Q becomes 1; if D is 0, Q becomes 0.
  • When the Enable (E) input is low (0), the latch is closed. It ignores the D input and holds (stores) its last value.
  • The D latch ensures that the illegal S=1, R=1 condition can never occur internally, making it safer to use.

1.3 Finite State Machines (FSM)

A Finite State Machine (FSM), or Finite Automaton, is an abstract model of computation used to design digital logic circuits and computer programs. An FSM is defined by a finite number of states and the transitions between those states. The SR latch is a perfect simple example of an FSM.

1.3.1 FSM Definitions

An FSM is an abstract machine that can be in exactly one of a finite number of states at any given time. Its behavior is defined by:

  1. States (\(S\)): A finite set of possible conditions the machine can be in (e.g., for the SR latch: Q=0, Q=1, uninitialized, invalid).
  2. Initial State (\(s_0\)): The state the machine starts in (e.g., uninitialized).
  3. Inputs (\(I\)): A finite set of input signals the machine can receive (e.g., the four possible combinations of S and R).
  4. Outputs (\(O\)): A finite set of output signals the machine can produce (e.g., the value of Q).
  5. Transition Function: A rule that determines the next state based on the current state and the current input.

This FSM is deterministic: for any given state and input, there is only one possible next state.

1.3.2 Visualizing FSMs

There are two common ways to represent an FSM:

  • State Transition Diagram: A directed graph where nodes represent states and arrows represent transitions. Each arrow is labeled with the input that causes the transition.
  • State Transition Table: A table that lists the next state and output for every possible combination of current state and input.

For the SR latch, the state diagram would show transitions from the Q=0 state to the Q=1 state on an S=1, R=0 input, and a loop back to itself on an S=0, R=0 input.

2. Definitions

  • Arithmetic-Logic Unit (ALU): A digital circuit that performs arithmetic (addition, subtraction) and logic (AND, OR, NOT) operations.
  • Multiplexer (MUX): A device that selects one of several analog or digital input signals and forwards the selected input into a single line.
  • Opcode: An operation code; a control signal that specifies the operation to be performed by a component like an ALU.
  • Full Adder: A combinational logic circuit that adds three input bits (A, B, Carry-in) and produces a two-bit output (Sum, Carry-out).
  • Ripple-Carry Adder: A type of binary adder constructed by cascading full adders, where the carry-out of each stage is connected to the carry-in of the next.
  • Partial Products: The intermediate results obtained in binary multiplication by ANDing the multiplicand with each bit of the multiplier.
  • Latch: A sequential logic circuit that can store one bit of information. It has two stable states and is the basic building block of memory.
  • Universal Gate: A logic gate (either NAND or NOR) from which any other logic function can be constructed.
  • SR Latch: A Set-Reset latch, a simple bistable multivibrator that can be set (to 1), reset (to 0), or hold its current state.
  • D Latch: A Data or “transparent” latch that passes its input to the output when enabled and holds its state when disabled, avoiding the illegal state of an SR latch.
  • Finite State Machine (FSM): A computational model consisting of a finite number of states, transitions between those states triggered by inputs, and actions or outputs.